P5517 [MtOI2019]幻想乡数学竞赛

发表于

闲扯

数列练习好题。

题面

P5517 [MtOI2019]幻想乡数学竞赛

Solution

直接暴力矩阵乘法肯定不行，复杂度爆了。

考虑简化，可以发现这个式子很有规律。

由高一的数列知识，我们做出如下操作：

我们设 $b_{i}=a_i-3\cdot a_{i-1}$ ，其中 $b_1=3,b_2=6$ 。

那么我们有：

我们分奇偶讨论：

当 $n$ 为奇数时，由累加法，我们有 $b_n-b_1=3^n+3^{n-2}+\cdots +3^3$ 。

等比数列求和，我们可以得到：

所以 $a_n-3\cdot a_{n-1}=\frac{3^{n+2}-3}{8}$ 。

类似的，我们可以算出当 $n$ 为偶数时， $a_n-3\cdot a_{n-1}=\frac{3^{n+2}-33}{8}$ 。

继续按照套路，我们设 $c_i=\frac{a_i}{3^i}$ ，则：

同样分奇偶讨论。

当 $n$ 为奇数时，我们有：

两式相加，可以得到 $c_n-c_{n-2}=\frac{9}{4}-\frac{17}{4\cdot 3^{n-1}}$ 。

继续使用累加法，我们有：

因为 $c_1=-2$ ，所以 $c_n=\frac{17}{32}\cdot 3^{1-n}+\frac{9}{8}n-\frac{117}{32}$ 。

所以当 $n$ 为奇数时， $a_n=\frac{51}{32}+\frac{n}{8}\cdot 3^{n+2}-\frac{117}{32}\cdot 3^n$ 。

类似的，我们可以推出当 $n$ 为偶数的时候， $a_n=\frac{21}{32}+\frac{n}{8}\cdot 3^{n+2}-\frac{117}{32}\cdot 3^n$ 。

可以发现只有常数项有细微的差别，我们合并一下，即可得到：

发现我们每次需要算一个 $3^n$ ，时间复杂度 $O(T\log n)$ ，依旧很爆炸。

根据费马小定理，我们有 $3^n\equiv 3^{n\ mod\ P-1}(mod\ P)$ ，可以优化到 $O(T\log P)$ 。然而并没有啥卵用

但是 $P=10^9+7,\sqrt{P}=31623$ ， 所以考虑光速幂。

我们预处理出 $3^{32000i}$ 和 $3^i$ ，就可以将 $3^n$ 拆分为 $3^{\lfloor\frac{n}{32000}\rfloor}\cdot 3^{n\ mod\ 32000}$ 。

这样就能 $O(1)$ 计算了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}namespace Mker{
	#include<climits>
	#define ull unsigned long long
	#define uint unsigned int
	ull sd;int op;
	inline void init() {read(sd),read(op);}
	inline ull ull_rand(){
		sd ^= sd << 43;
		sd ^= sd >> 29;
		sd ^= sd << 34;
		return sd;
	}
	inline ull rand(){
		if (op == 0) return ull_rand() % USHRT_MAX + 1;
		if (op == 1) return ull_rand() % UINT_MAX + 1; 
		if (op == 2) return ull_rand();
		return 0;
	}
}
const int MAXN = 32e3+5,mod = 1e9+7;
const int inv32 = 281250002,Pow = 369057345;
int T,pw[MAXN],pw1[MAXN],ans;
it add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
it mul(int x,int y){return 1ll*x*y%mod;}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(T);Mker::init();
	pw[0]=pw1[0]=1;
	for(ri i=1;i<=32000;++i)
		pw[i]=mul(pw[i-1],Pow),pw1[i]=mul(pw1[i-1],3);
	for(ri i=1;i<=T;++i){
		unsigned ll n=Mker::rand(),m=n%(mod-1);
		int res=mul(n%mod,36);
		res=add(res,mod-117);
		res=mul(mul(pw[m/32000],pw1[m%32000]),res);
		res=add(res,(n&1ull)?51:21),res=mul(res,inv32);
		ans^=res;
	}
	print(ans);
	return 0;
}